//#include <iostream>
//#include <fstream>
//#include <vector>
//#include <algorithm>
//#include <set>
//
//using namespace std;
//
//struct Point {
//    int x, y;
//};
//
//bool compareX(Point p1, Point p2) {
//    return (p1.x < p2.x) || (p1.x == p2.x && p1.y < p2.y);
//}
//
//bool compareY(Point p1, Point p2) {
//    return p1.y < p2.y;
//}
//
//int orientation(Point p, Point q, Point r) {
//    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
//    if (val == 0) return 0;  // colinear
//    return (val > 0) ? 1 : 2; // clockwise or counterclockwise
//}
//
//void merge(vector<Point>& points, int left, int mid, int right, set<Point, decltype(compareY)*>& result) {
//    int n1 = mid - left + 1;
//    int n2 = right - mid;
//
//    vector<Point> leftSubset(points.begin() + left, points.begin() + left + n1);
//    vector<Point> rightSubset(points.begin() + mid + 1, points.begin() + mid + 1 + n2);
//
//    int i = 0, j = 0, k = left;
//
//    while (i < n1 && j < n2) {
//        if (compareY(leftSubset[i], rightSubset[j])) {
//            points[k++] = leftSubset[i++];
//        } else {
//            points[k++] = rightSubset[j++];
//        }
//    }
//
//    while (i < n1) {
//        points[k++] = leftSubset[i++];
//    }
//
//    while (j < n2) {
//        points[k++] = rightSubset[j++];
//    }
//
//    result.clear();
//    for (int p = left; p <= right; ++p) {
//        result.insert(points[p]);
//    }
//}
//
//vector<Point> findConvexHull(vector<Point>& points, int left, int right) {
//    set<Point, decltype(compareY)*> uniquePoints(compareY);
//
//    if (right - left + 1 <= 3) {
//        // If there are 3 or fewer points, simply return them as the convex hull
//        for (int i = left; i <= right; ++i) {
//            uniquePoints.insert(points[i]);
//        }
//
//        return vector<Point>(uniquePoints.begin(), uniquePoints.end());
//    }
//
//    int mid = (left + right) / 2;
//
//    vector<Point> leftHull = findConvexHull(points, left, mid);
//    vector<Point> rightHull = findConvexHull(points, mid + 1, right);
//
//    vector<Point> result;
//    merge(points, left, mid, right, uniquePoints);
//
//    int i = 0, j = 0;
//    int n1 = leftHull.size();
//    int n2 = rightHull.size();
//
//    while (i < n1 && j < n2) {
//        if (orientation(*uniquePoints.begin(), leftHull[i], rightHull[j]) == 1) {
//            uniquePoints.insert(leftHull[i++]);
//        } else {
//            uniquePoints.insert(rightHull[j++]);
//        }
//    }
//
//    while (i < n1) {
//        uniquePoints.insert(leftHull[i++]);
//    }
//
//    while (j < n2) {
//        uniquePoints.insert(rightHull[j++]);
//    }
//
//    return vector<Point>(uniquePoints.begin(), uniquePoints.end());
//}
//
//vector<Point> convexHullDivideAndConquer(vector<Point>& points) {
//    sort(points.begin(), points.end(), compareX);
//
//    return findConvexHull(points, 0, points.size() - 1);
//}
//
//vector<Point> readPointsFromFile(const string& filePath) {
//    vector<Point> points;
//    ifstream file(filePath);
//
//    int x, y;
//    while (file >> x >> y) {
//        Point point = {x, y};
//        points.push_back(point);
//    }
//
//    file.close();
//    return points;
//}
//
//void savePointsToFile(const string& filePath, const vector<Point>& points) {
//    ofstream file(filePath);
//
//    for (const Point& point : points) {
//        file << point.x << " " << point.y << "\n";
//    }
//
//    file.close();
//}
//
//int main() {
//    string filePath = "random_points_100.txt";
//
//    // 从文件中读取点
//    vector<Point> points = readPointsFromFile(filePath);
//
//    // 使用分治法求解凸包
//    vector<Point> convexHull = convexHullDivideAndConquer(points);
//
//    // 保存凸包点集到文件
//    savePointsToFile("convex_hull_output.txt", convexHull);
//
//    // 输出结果
//    cout << "Convex Hull Points:\n";
//    for (const Point& point : convexHull) {
//        cout << "(" << point.x << ", " << point.y << ")\n";
//    }
//
//    return 0;
//}
